package ebook.datastructure.typed.chapter12;

import java.util.Arrays;

/**
 * description: <br>
 * createTime: 2020/9/19:24 <br>
 *
 * @author zzh
 */
public class HeapByArray<T extends Comparable> implements Heap<T> {
    Object[] array;

    int size = 0;

    private static final int DEFAULT_CAPACITY = 50;


    public HeapByArray() {
        this(DEFAULT_CAPACITY);
    }

    public HeapByArray(int capacity) {
        this.array = new Object[capacity];
    }


    @Override
    public boolean insert(T t) {
        if(size == array.length) {
            return false;
        }
        array[size] = t;
        trickleUp(size++);
        return true;
    }


    @Override
    public T delete() {
        T root = (T) array[0];
        array[0] = array[--size];
        array[size] = null;
        trickleDown(0);
        return root;
    }


    public void changePriority(int index, T newValue) {
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("index:" + index+ " is illegal");
        }
        T oldValue = (T) array[index];
        array[index] = newValue;
        int result = oldValue.compareTo(newValue);
        if(result > 0) {
            trickleDown(index);
        } else if(result < 0) {
            trickleUp(index);
        }
    }


    private void trickleUp(int index) {
        T value = (T) array[index];
        int lastIndex = index;
        int parentIndex = (lastIndex - 1) / 2;
        while(lastIndex > 0 && ((T)array[parentIndex]).compareTo(value) < 0) {
            array[lastIndex] = array[parentIndex];
            lastIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        array[lastIndex] = value;
    }

    private void trickleDown(int index) {
        T value = (T) array[index];
        int currentIndex = index;
        int leftSonIndex = (2 * currentIndex) + 1;
        int rightSonIndex = (2 * currentIndex) + 2;
        while(leftSonIndex < size) {
            // 先确定哪个子节点大，再与父节点比较，
            int largerIndex;
            if(rightSonIndex > size - 1) {
                // 只有左节点
                largerIndex = leftSonIndex;
            } else {
                if(((T) array[leftSonIndex]).compareTo(((T) array[rightSonIndex])) > 0) {
                    largerIndex = leftSonIndex;
                } else {
                    largerIndex = rightSonIndex;
                }
            }
            if(((T) array[largerIndex]).compareTo(value) > 0) {
                // 交换
                array[currentIndex] = array[largerIndex];
                currentIndex = largerIndex;
                leftSonIndex = (2 * currentIndex) + 1;
                rightSonIndex = (2 * currentIndex) + 2;
            } else {
                break;
            }
        }
        array[currentIndex] = value;
    }


    @Override
    public String toString() {
        return Arrays.toString(array);
    }


    public static void main(String[] args) {
        HeapByArray<Integer> heap = new HeapByArray(15);
        heap.insert(1000);
        System.out.println(heap);
        heap.insert(500);
        System.out.println(heap);
        heap.insert(600);
        System.out.println(heap);
        heap.insert(700);
        System.out.println(heap);
        heap.insert(1000);
        System.out.println(heap);
        heap.delete();
        System.out.println(heap);
        heap.insert(4500);
        System.out.println(heap);
        heap.insert(350);
        System.out.println(heap);
        heap.delete();
        System.out.println(heap);
        heap.delete();
        System.out.println(heap);
        heap.changePriority(2, 1600);
        System.out.println(heap);
    }
}
